home *** CD-ROM | disk | FTP | other *** search
/ Aminet 30 / Aminet 30 (1999)(Schatztruhe)[!][Apr 1999].iso / Aminet / dev / lang / SmallEiffel.lha / SmallEiffel / lib_std / link2_list.e < prev    next >
Text File  |  1998-12-22  |  4KB  |  175 lines
  1. -- This file is  free  software, which  comes  along  with  SmallEiffel. This
  2. -- software  is  distributed  in the hope that it will be useful, but WITHOUT 
  3. -- ANY  WARRANTY;  without  even  the  implied warranty of MERCHANTABILITY or
  4. -- FITNESS  FOR A PARTICULAR PURPOSE. You can modify it as you want, provided
  5. -- this header is kept unaltered, and a notification of the changes is added.
  6. -- You  are  allowed  to  redistribute  it and sell it, alone or as a part of 
  7. -- another product.
  8. --          Copyright (C) 1994-98 LORIA - UHP - CRIN - INRIA - FRANCE
  9. --            Dominique COLNET and Suzanne COLLIN - colnet@loria.fr 
  10. --                       http://www.loria.fr/SmallEiffel
  11. --
  12. class LINK2_LIST[E]
  13.    -- 
  14.    -- Two way linked list with internal automatic memorization of 
  15.    -- the last access.
  16.    --
  17.  
  18. inherit LINKED_COLLECTION[E] redefine first_link end;
  19.  
  20. creation
  21.    make, from_collection
  22.  
  23. feature {LINKED_COLLECTION}
  24.    
  25.    first_link: LINK2[E];
  26.  
  27. feature -- Creation and Modification :
  28.    
  29.    make is
  30.       -- Make an empty list;
  31.       do
  32.      first_link := Void;
  33.      last_link := Void;
  34.      upper := 0;
  35.      mem_idx := 0;
  36.      mem_lnk := Void;
  37.       ensure
  38.      count = 0
  39.       end;
  40.  
  41. feature -- Implementation of deferred :
  42.  
  43.    add_first(element: like item) is
  44.       do
  45.      if first_link = Void then
  46.         !!first_link.make(element,Void,Void);
  47.         last_link := first_link;
  48.         upper := 1;
  49.         mem_idx := 1;
  50.         mem_lnk := first_link;
  51.      else
  52.         !!first_link.make(element,Void,first_link);
  53.         first_link.next.set_previous(first_link);
  54.         upper := upper + 1;
  55.         mem_idx := mem_idx + 1;
  56.      end;
  57.       ensure then
  58.      upper = 1 + old upper 
  59.       end;
  60.  
  61.    add_last(element: like item) is
  62.       do
  63.      if first_link = Void then
  64.         !!first_link.make(element,Void,Void);
  65.         last_link := first_link;
  66.         upper := 1;
  67.         mem_idx := 1;
  68.         mem_lnk := first_link;
  69.      else
  70.         !!last_link.make(element,last_link,Void);
  71.         last_link.previous.set_next(last_link);
  72.         upper := upper + 1;
  73.      end;
  74.       end;
  75.  
  76.    add(element: like item; index: INTEGER) is
  77.       local
  78.      link: like first_link;
  79.       do
  80.      if index = 1 then
  81.         add_first(element);
  82.      elseif index = upper + 1 then
  83.         add_last(element);
  84.      else
  85.         if (index - 1) /= mem_idx then
  86.            go_item(index - 1);
  87.         end;
  88.         !!link.make(element,mem_lnk,mem_lnk.next);
  89.         link.next.set_previous(link);
  90.         mem_lnk.set_next(link);
  91.         upper := upper + 1;
  92.      end;
  93.       end;
  94.  
  95.    remove_first is
  96.       do
  97.      if upper = 1 then
  98.         make;
  99.      else
  100.         mem_lnk := first_link;
  101.         first_link := first_link.next;
  102.         first_link.set_previous(Void);
  103.         mem_lnk := first_link;
  104.         mem_idx := 1;
  105.         upper := upper - 1;
  106.      end;
  107.       end;
  108.  
  109.    remove(index: INTEGER) is
  110.       local
  111.      link: like first_link;
  112.       do
  113.      if index = 1 then
  114.         remove_first;
  115.      elseif index = upper then
  116.         remove_last;
  117.      else
  118.         if (index - 1) /= mem_idx then
  119.            go_item(index - 1);
  120.         end;
  121.         link := mem_lnk.next;
  122.         mem_lnk.set_next(link.next);
  123.         link.next.set_previous(mem_lnk);
  124.         upper := upper - 1;
  125.      end;
  126.       end;
  127.  
  128. feature {NONE}
  129.  
  130.    go_item(index: INTEGER) is
  131.       do
  132.      if index > mem_idx then
  133.         if (upper - index) < (index - mem_idx) then
  134.            from
  135.           mem_idx := upper;
  136.           mem_lnk := last_link;
  137.            until
  138.           index = mem_idx
  139.            loop
  140.           mem_lnk := mem_lnk.previous;
  141.           mem_idx := mem_idx - 1;
  142.            end;
  143.         else
  144.            from
  145.            until
  146.           index = mem_idx
  147.            loop
  148.           mem_lnk := mem_lnk.next;
  149.           mem_idx := mem_idx + 1;
  150.            end;
  151.         end
  152.      elseif (mem_idx - index) < (index - 1) then
  153.         from
  154.         until
  155.            index = mem_idx
  156.         loop
  157.            mem_lnk := mem_lnk.previous;
  158.            mem_idx := mem_idx - 1;
  159.         end;
  160.      else
  161.         from
  162.            mem_idx := 1;
  163.            mem_lnk := first_link;
  164.         until
  165.            index = mem_idx
  166.         loop
  167.            mem_lnk := mem_lnk.next;
  168.            mem_idx := mem_idx + 1;
  169.         end;
  170.      end;
  171.       end;
  172.  
  173. end -- LINK2_LIST[E]
  174.  
  175.